#include "./shortest-path.h"

void dijkstra(MGraph &graph, int v, int *pathArc, int *shortTable)
{
	// 先初始化所有辅助储存数组
	// 例如included[1] = 1则表示起点和下标为1的点之间的最短路径已被求出，下标为1的点被加入了已知点集
	int included[graph.vexNum];
	for (int i = 0; i < graph.vexNum; i++)
	{
		included[i] = 0;				  // 全部顶点现在还处于未知状态
		pathArc[i] = -1;				  // 初始化最短路径终点前驱下标全为-1表示还没找到最短路径
		shortTable[i] = graph.edge[v][i]; // 将与起点连线的顶点加上权值作为目前的最短路径
	}
	// 起点v不需要和自己求最短路径，因此修改上述数组
	included[v] = 1;
	shortTable[v] = 0;
	// 开始主循环，每次求得v到遍历的顶点i的路径
	int currentFind; // 记录每一趟找到的点的下标
	int min;		 // 记录这一趟的当前所知离v的最短距离
	for (int i = 0; i < graph.vexNum; i++)
	{
		// 跳过起点自己
		if (i == v)
		{
			continue;
		}
		min = INFINITY;
		// 寻找距离v最近的顶点
		for (int j = 0; j < graph.vexNum; j++)
		{
			if (!included[j] && shortTable[j] < min)
			{
				currentFind = j;
				min = shortTable[j];
			}
		}
		// 把目前找到的顶点加入到已知点集
		included[currentFind] = 1;
		// 修正当前最短距离与路径
		// 也就是再上述循环找到最短路径点currentFind的基础上，进一步对currentFind的其它邻接点进行计算，得到v与这些邻接点的路径和
		for (int j = 0; j < graph.vexNum; j++)
		{
			// 如果说v到这些邻接点的距离小于最短路径表中的距离，则进行更新
			if (!included[j] && (min + graph.edge[currentFind][j] < shortTable[j]))
			{
				shortTable[j] = min + graph.edge[currentFind][j];
				pathArc[j] = currentFind;
			}
		}
	}
}

void floyd(MGraph &graph, int **pathArc, int **shortTable)
{
	// 先初始化所有数组
	for (int i = 0; i < graph.vexNum; i++)
	{
		for (int j = 0; j < graph.vexNum; j++)
		{
			shortTable[i][j] = graph.edge[i][j];
			pathArc[i][j] = j;
		}
	}
	// 计算最短路径
	// i表示中转顶点下标，j代表起始顶点下标，k表示结束顶点下标
	// 例如i=0时，会计算所有顶点中转经过下标为0的顶点的长度是否小于起点到终点的直接长度，若小于则把j到k的顶点最短路径记为这个中转长度，与此同时前驱数组也进行相应的修改
	for (int i = 0; i < graph.vexNum; i++)
	{
		for (int j = 0; j < graph.vexNum; j++)
		{
			for (int k = 0; k < graph.vexNum; k++)
			{
				if (shortTable[j][k] > shortTable[j][i] + shortTable[i][k])
				{
					shortTable[j][k] = shortTable[j][i] + shortTable[i][k];
					pathArc[j][k] = pathArc[j][i];
				}
			}
		}
	}
}